﻿using System;
using System.Collections.Generic;

namespace HeroDream
{
    /// <summary>
    /// 排序类
    /// 静态类不用生成对象，通过静态方法直接调用，一般用于工具类
    /// </summary>
    static  class SortUtils
    {
        public static void Test()
        {
            int[] array = new int[] { 3, 21, 12, 9, 15, 2, 18, 7 };
            SortUtils.MergeSort(array, 0, array.Length - 1);
            List<int> l = new List<int> { 3, 21, 12, 9, 15, 2, 18, 7 };
            l.Sort();
            l.RemoveAt(0);
            foreach (var v in array)
            {
                Console.WriteLine(v);
            }
        }

        /// <summary>
        /// 冒泡排序,时间复杂度为O(n^2)
        /// </summary>
        /// <param name="array"></param>
        /// <param name="len"></param>
        public static void BubbleSort(int[] array,int len)
        {
            for(int i = 0; i < len; i++)//对len个元素进行排序
            {
                //每次循环把最大的元素冒泡到最后边来。
                //当i为2的时候，代表我们执行完两次了，找出了最大的两个元素，把最大的两个元素放在最后边，
                //这个时候j需要从0到(总个数-已排序个数)之间进行冒泡出最大的数据来。即从0到3两两交换，把最大的元素放到3那个位置去。
                for (int j = 0; j < len-i-1; j++)
                {
                    if (array[j+1]>array[j])
                    {
                        int temp = array[j+1];
                        array[j+1] = array[j];
                        array[j] = temp;
                    }
                }
            }
        }

        /// <summary>
        /// 插入排序 时间复杂度为O(n^2）
        /// </summary>
        /// <param name="array"></param>
        /// <param name="len"></param>
        public static void InsertSort(int[] array, int len)
        {
            for(int i = 0; i < len; i++)//对len个元素进行排序
            {
                //取出待插入的数据
                int temp = array[i];
                //从已排序数据中（0到i-1个数据已排序了），从后向前扫描
                int j = i - 1;//定义数据j,当每个
                for(j = i - 1; j >= 0; j--)
                {
                    if (array[j] > temp)//如果当前值大于待插入的值，则把当前值向后移动一位
                    {
                        array[j + 1] = array[j];
                    }
                    else//否则代表当前值小于待插入的值了，这个时候就需要把新值插入到当前值（array[j]）的后边。
                    {
                     // array[j + 1] = temp;
                        break;
                    }
                }
              array[j + 1] = temp;
            }
        }

        /// <summary>
        /// 归并排序
        /// </summary>
        /// <param name="array"></param>
        /// <param name="left"></param>
        /// <param name="right"></param>
        public static void MergeSort(int[] array,int left,int right)
        {
            if (left == right ) return;
            int mid = left + (right - left) / 2;
            //拆分
            MergeSort(array, left, mid);
            MergeSort(array, mid+1,right );
            //归并
            //将数据进行合并
            //将left到mid和mid到right的值进行归并
            MergeData(array, left, mid, right);
        }

        private static void MergeData(int[] array, int left,int mid, int right )
        {
            int[] sortArray = new int[array.Length];
            int leftRef = left;
            int rightRef = mid+1;
            int sortIndex = leftRef;
            while (sortIndex <= right)
            {
                if(leftRef > mid)
                {
                    sortArray[sortIndex] = array[rightRef++];
                }
               else  if (rightRef > right)
                {
                    sortArray[sortIndex] = array[leftRef++];
                }
                else if (array[leftRef] < array[rightRef])
                {
                    sortArray[sortIndex] = array[leftRef++];
                }
                else
                {
                    sortArray[sortIndex] = array[rightRef++];
                }
                sortIndex++;
            }

            for (int i = left; i <= right; i++)
            {
                array[i] = sortArray[i];
            }
        }

        /// <summary>
        /// 定义一个比较两个Int数大小的方法，如果A>B，返回-1，A<B返回1，A=B,返回0
        /// </summary>
        public static int Number(int A, int B)
        {
            if (A > B)
            {
                return -1;
            }
            else if (A < B)
            {
                return 1;
            }
            else
            {
                return 0;
            }
        }

        //比较装备大小的排序规则
        //如果装备A的战斗力大于B的战斗力，返回1，小于返回-1，相等返回0；
        public static int Daew(Equipment A, Equipment B)
        {
            if (A.Price <B.Price)
            {
                return -1;
            }
            else if (A.Price > B.Price)
            {
                return 1;
            }
            else
            {
                return 0;
            }
        }
    }
}
